package com.c2b.algorithm.leetcode.base;

/**
 * <a href="https://leetcode.cn/problems/max-consecutive-ones-iii/">最大连续1的个数 III(Max Consecutive Ones III)</a>
 * <p>给定一个二进制数组 nums 和一个整数 k，如果可以翻转最多 k 个 0 ，则返回 数组中连续 1 的最大个数 。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：nums = [1,1,1,0,0,0,1,1,1,1,0], K = 2
 *      输出：6
 *      解释：[1,1,1,0,0,1,1,1,1,1,1]
 *      粗体数字从 0 翻转到 1，最长的子数组长度为 6。
 *
 * 示例 2：
 *      输入：nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3
 *      输出：10
 *      解释：[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
 *      粗体数字从 0 翻转到 1，最长的子数组长度为 10。
 * </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>1 <= nums.length <= 10^5</li>
 *     <li>nums[i] 不是 0 就是 1</li>
 *     <li>0 <= k <= nums.length</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2024/2/21 16:53
 */
public class LC1004MaxConsecutiveOnes_III_M {

    static class Solution {
        /**
         * 滑动窗口：转化为窗口最多运行 k 个 0
         */
        public int longestOnes(int[] nums, int k) {
            int res = 0;
            // 滑动窗口内 0 的个数
            int zeroNums = 0;
            // 左边界
            int left = 0;
            // 右边界
            for (int right = 0; right < nums.length; ++right) {
                if (nums[right] == 0) {
                    ++zeroNums;
                }
                while (zeroNums > k) {
                    if (nums[left] == 0) {
                        --zeroNums;
                    }
                    ++left;
                }
                res = Math.max(res, right - left + 1);
            }
            return res;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.longestOnes(new int[]{1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0}, 2));
        System.out.println(solution.longestOnes(new int[]{0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1}, 3));
    }
}
